#include "./ad-list.h"
#include <stdio.h>
#include <stdlib.h>

AdList createAdList()
{
	AdList list = (AdList)malloc(sizeof(GraphAdList));
	list->edgeNum = list->vertexNum = 0;
	return list;
}

int adListLocateVex(AdList adList, char v)
{
	int i;
	for (i = 0; i < adList->vertexNum; i++)
	{
		if (adList->vertexs[i].data == v)
		{
			return i;
		}
	}
	return -1;
}

int adListFirstAdjVex(AdList adList, int v)
{
	EdgeNode *next = adList->vertexs[v].firstEdge;
	return next == NULL ? -1 : next->adjvex;
}

void adListInsertVex(AdList adList, char v)
{
	adList->vertexs[adList->vertexNum].in = 0;
	adList->vertexs[adList->vertexNum].data = v;
	adList->vertexs[adList->vertexNum].firstEdge = NULL;
	adList->vertexNum++;
}

void adListInsertArc(AdList adList, int v, int w, int weight)
{
	EdgeNode *node = adList->vertexs[v].firstEdge, *newNode;
	newNode = (EdgeNode *)malloc(sizeof(EdgeNode));
	newNode->adjvex = w;
	newNode->weight = weight;
	newNode->next = NULL;
	// 若该点没有邻接点直接插入
	if (node == NULL)
	{
		adList->vertexs[v].firstEdge = newNode;
	}
	else
	{
		// 否则寻找至最后一点
		while (node->next != NULL)
		{
			node = node->next;
		}
		node->next = newNode;
	}
	// 终点入度加一
	adList->vertexs[w].in++;
	adList->edgeNum++;
}

#ifndef CHECK_VISIT
#define CHECK_VISIT

/// @brief 检查辅助数组中是否还有没访问到的
/// @param visit 访问辅助数组
/// @param length 顶点个数
/// @return 若有没访问到的返回其下标，否则返回-1
int checkVisit(int visit[], int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		if (!visit[i])
		{
			return i;
		}
	}
	return -1;
}

#endif

void adListDFS(AdList adList, int start, int visit[])
{
	// 先访问起始点
	printf("%c ", adList->vertexs[start].data);
	visit[start] = 1;
	EdgeNode *pointer = adList->vertexs[start].firstEdge;
	while (pointer != NULL)
	{
		// 递归访问没被访问的点
		if (!visit[pointer->adjvex])
		{
			adListDFS(adList, pointer->adjvex, visit);
		}
		// 否则找下一个邻接点
		pointer = pointer->next;
	}
}

void adListDFSTraverse(AdList adList)
{
	// 初始化辅助数据
	int visit[adList->vertexNum], i, notVisited;
	for (i = 0; i < adList->vertexNum; i++)
	{
		visit[i] = 0;
	}
	// 开始访问
	for (notVisited = checkVisit(visit, adList->vertexNum); notVisited != -1; notVisited = checkVisit(visit, adList->vertexNum))
	{
		adListDFS(adList, notVisited, visit);
	}
	printf("\n");
}

void adListBFSTraverse(AdList adList)
{
	// 初始化辅助数据
	int visit[adList->vertexNum], i, notVisited, temp;
	for (i = 0; i < adList->vertexNum; i++)
	{
		visit[i] = 0;
	}
	// 初始化循环队列
	int queueMax = 100, queue[queueMax], rear = 0, front = 0;
	// 开始访问
	EdgeNode *pointer;
	for (notVisited = checkVisit(visit, adList->vertexNum); notVisited != -1; notVisited = checkVisit(visit, adList->vertexNum))
	{
		// 广度优先遍历，进队前先访问
		// 先访问第一个点并进队列
		printf("%c ", adList->vertexs[notVisited].data);
		visit[notVisited] = 1;
		queue[rear] = notVisited;
		rear = (rear + 1) % queueMax;
		// 依次出队并将出队顶点邻接点进队列
		while (rear != front)
		{
			// 出队
			temp = queue[front];
			front = (front + 1) % queueMax;
			// 未访问的邻接点访问并进队
			pointer = adList->vertexs[temp].firstEdge;
			while (pointer != NULL)
			{
				if (!visit[pointer->adjvex])
				{
					printf("%c ", adList->vertexs[pointer->adjvex].data);
					visit[pointer->adjvex] = 1;
					queue[rear] = pointer->adjvex;
					rear = (rear + 1) % queueMax;
				}
				// 已访问则查看下一个邻接点
				pointer = pointer->next;
			}
		}
	}
	printf("\n");
}

void printAdList(AdList adList)
{
	EdgeNode *pointer;
	int i;
	printf("顶点 -> 邻接点下标:权值 -> ... -> ^\n");
	printf("|-------------------------------|\n");
	for (i = 0; i < adList->vertexNum; i++)
	{
		printf("%c ->", adList->vertexs[i].data);
		pointer = adList->vertexs[i].firstEdge;
		while (pointer != NULL)
		{
			printf(" %d:%d ->", pointer->adjvex, pointer->weight);
			pointer = pointer->next;
		}
		printf(" ^\n");
	}
}